n=3
def is_re(str_s):
    stack_list=[]
    i=0
    while i<len(str_s):
        if str_s[i]=="(":
            stack_list.append(str_s[i])
        else:
            #做一次弹出操作
            if len(stack_list)==0:
                return False
            stack_list.pop()
        i+=1
    if len(stack_list)==0:
        return True
    else:
        return False
#先写一个最简单的回溯算法
def dfs(str_s,size,depth,state,path,res):
    if depth==size:
        #此时表示已经满了
        if path not in res:
            if is_re(path):
                res.append(path[:])
        return None
    #开始正常情况
    for i in range(size):
        if not state[i]:
            # print("")
            state[i]=True
            path+=str_s[i]
            dfs(str_s,size,depth+1,state,path,res)
            path=path[:len(path)-1]
            state[i]=False
#该方法要把所有可能性都走一遍，所以整个过程非常复杂
def generateParenthesis(n):
    if n==1:
        return ["()"]
    str_s="()"*n
    # print(str_s)
    #状态序列部分
    state=[False for _ in range(n*2)]
    res=[]
    depth=0  #深度
    path=""
    dfs(str_s,2*n,depth,state,path,res)
    for i in res:
        print(i)
# generateParenthesis(n)
#先写一个最简单的回溯算法
def dfs_1(str_s,size,depth,path,res):
    if depth==size:
        #此时表示已经满了
        if path not in res:
            if is_re(path):
                res.append(path[:])
        return None
    #开始正常情况
    # for i in range(size):
    for i in range(2):
        # if not state[i]:
            # print("")
            # state[i]=True
        path+=str_s[i]
        dfs_1(str_s,size,depth+1,path,res)
        path=path[:len(path)-1]
            # state[i]=False
#该方法要把所有可能性都走一遍，所以整个过程非常复杂
def generateParenthesis_1(n):
    if n==1:
        return ["()"]
    str_s="()"
    # print(str_s)
    #状态序列部分
    # state=[False for _ in range(n*2)]
    res=[]
    depth=0  #深度
    path=""
    dfs_1(str_s,2*n,depth,path,res)
    for i in res:
        print(i)
# generateParenthesis_1(n)
#第三种实现方法：这里依旧使用的是回溯法
def dfs_2(str_s,left_num,right_num,path,res):
    if left_num==0 and right_num==0:
        #全部的符号都已经用完了
        res.append(path[:])
        return None
    for s in str_s:
        if s=="(" and left_num>0:
            left_num-=1
            path+="("
            dfs_2(str_s,left_num,right_num,path,res)
            left_num+=1
            path=path[:len(path)-1]
        if s==")" and left_num<right_num and right_num>0:
            right_num-=1
            path+=")"
            dfs_2(str_s,left_num,right_num,path,res)
            right_num+=1
            path=path[:len(path)-1]
def generateParenthesis_2(n):
    #定义存放左右括号剩余数量的变量
    left_num,right_num=n,n
    path=""  #用来存放当前的路径信息
    res=[]  #用来存放结果集合
    dfs_2("()",left_num,right_num,path,res)
    print(res)

generateParenthesis_2(n)






